home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / science / laame101.zip / MAN.TXT < prev    next >
Text File  |  1994-02-23  |  55KB  |  959 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.            **         ***        ***        **     **  ********  *******
  13.           **         ****       ****       ** * * **  ********  ********
  14.          **         ** **      ** **      **  ** **  **        **     **
  15.         **         **  **     **  **     **     **  ****      ********
  16.        **         *******    *******    **     **  **        **     **
  17.       *********  **    **   **    **   **     **  ********  ********
  18.      *********  **     **  **     **  **     **  ********  ********
  19.  
  20.  
  21.  
  22.  
  23.  
  24.   Laboratorio di Analisi Algoritmi di Minimizzazione di Espressione Booleane
  25.  
  26.                                       by
  27.  
  28.                                 Giuliano Bossi
  29.                                Vincenzo Brescia
  30.                                Federica Molinari
  31.  
  32.                                  Versione 1.01
  33.  
  34.  
  35.          LAAMEB  nella sua versione 1.01 e' distribuito secondo il
  36.          criterio  SHAREWARE,  che  permette agli utenti di provare un
  37.          prodotto prima di decidere per un suo eventuale acquisto.
  38.  
  39.          L'unica differenza nelle  versioni  SHAREWARE  e  REGISTERED,
  40.          consiste   nell'impossibilita' dell'utente a salvare o
  41.      caricare funzioni booleane in formato file. Inoltre,  gli utenti
  42.      registrati  potranno  avere una  descrizione dettagliata degli
  43.      algoritmi  utilizzati e  della loro  implementazione.
  44.  
  45.          Viene  peraltro  incoraggiata la distribuzione di LAAMEB,
  46.          purche' esso venga distribuito nella sua  forma  originale, e
  47.          senza modifiche all'eseguibile e/o alla documentazione.
  48.  
  49.          Nessun  compenso  deve  essere richiesto o corrisposto per la
  50.          diffusione del pacchetto SHAREWARE di LAAMEB  tranne  per  le
  51.          spese sostenute  per la  sua duplicazione,  e comunque per un
  52.          costo non superiore alla quota di registrazione.
  53.  
  54.          Viene richiesto all'utilizzatore di registrare la sua licenza
  55.          d'uso presso gli autori.
  56.          La richiesta della licenza d'uso, che implica il pagamento di
  57.          una quota di registrazione pari a lire 30000,  permettera' al
  58.          possessore   di   usufruire   delle  piene  potenzialita' del
  59.          programma per quanto  riguardarda le routine  di  salvataggio
  60.          e caricamento di file di funzioni booleane.
  61.  
  62.          La richiesta di licenza d'uso puo' essere  effettuata tramite
  63.          matrix  al seguente indirizzo Fidonet:
  64.  
  65.                   Giuliano Bossi      2:331/308.8@Fidonet.Org
  66.  
  67.      Oppure  al seguente  indirizzo Internet, via e-mail:
  68.  
  69.           Giuliano Bossi      bossi@ghost.dsi.unimi.it
  70.  
  71.          Oppure  mediante  busta  chiusa  indirizzata a:
  72.  
  73.                                  Giuliano Bossi
  74.                                  Via Fermi, 14
  75.                                  22050 Lomagna (CO)
  76.                  ITALIA
  77.  
  78.          Nella richiesta dovranno essere precisati :
  79.          Il  Cognome e Nome  dell'utente, il suo  eventuale  indirizzo
  80.          Fidonet a 4 dimensioni, ed un suo recapito telefonico.
  81.  
  82.          Gli autori non risponderanno  ad eventuali  messaggi riguardo
  83.          all'utilizzo di  LAAMEB,  inviati da  utenti che  non abbiano
  84.          provveduto a registrarsi.
  85.      Eventuali  bug  possono  essere segnalati  a  Giuliano  Bossi
  86.      attraverso  una delle    modalita' riportate  sopra. Per quanto
  87.      possibile gli autori cercheranno di porvi rimedio.
  88.  
  89.      Oltre    a  questo  e  a  quanto  riportato  sopra non esistono
  90.          limitazioni all'uso di LAAMEB legate alla non registrazione.
  91.  
  92.          Benche'  il programma sia stato lungamente testato da un pool
  93.          di  Beta  Tester  gli autori  non  possono assumersi   alcuna
  94.          responsabilita' per danni dovuti all'utilizzo del programma.
  95.  LAAMEB 1.01                                                        pag.  3
  96.  
  97.  INDICE:
  98.  
  99.     0 Ringraziamenti.................................................pag.  4
  100.  
  101.     1 Introduzione...................................................pag.  4
  102.         1.0 L'aritmetica booleana....................................pag.  4
  103.         1.1 Che cos'e' LAAMEB?.......................................pag.  6
  104.         1.2 L'algoritmo di minimizzazione di Quine-McCluskey.........pag.  6
  105.         1.3 Aspetti di implementazione dell'algoritmo................pag.  7
  106.  
  107.     2 Come usare LAAMEB..............................................pag.  9
  108.         2.0 Le varie funzionalita' del programma.....................pag.  9
  109.         2.1 Il menu' File............................................pag.  9
  110.             2.1.0 Il comando Carica..................................pag.  9
  111.             2.1.1 Il comando Salva...................................pag. 10
  112.             2.1.2 Il comando Esci....................................pag. 10
  113.         2.2 Il menu' Funzione........................................pag. 11
  114.             2.2.0 Il comando Immetti.................................pag. 11
  115.             2.2.1 Il comando Calcola.................................pag. 11
  116.             2.2.2 Il comando Copertura...............................pag. 12
  117.             2.2.3 Il comando Statistica..............................pag. 12
  118.             2.2.4 Il comando Cancella................................pag. 12
  119.         2.3 Il menu' Algoritmo.......................................pag. 12
  120.  
  121.     3 LAAMEB al lavoro...............................................pag. 13
  122.         3.0 Interpretazione dei risultati............................pag. 13
  123.         3.1 Alcuni esempi interessanti...............................pag. 14
  124.  
  125.     4 Prospettive....................................................pag. 15
  126.         4.0 Come e' nato LAAMEB......................................pag. 16
  127.         4.1 Come potra' evolversi....................................pag. 16
  128.  
  129.     5 Bibliografia...................................................pag. 16
  130.  
  131.  LAAMEB 1.01                                                        pag.  4
  132.  
  133.  0 RINGRAZIAMENTI
  134.  
  135.  Gli autori desiderano ringraziare il prof. Mario Torelli del Dipartimento di
  136.  Scienze dell'Informazione di Milano e Aaron Brancotti per gli utili consigli
  137.  che hanno saputo dare a livello di implementazione del progetto.
  138.  Un grosso grazie deve essere rivolto a Luca Ciastellardi, Pietro Toniolo,
  139.  Andrea Biardi, Luigi Cristiano e tutto il clan di Euforia (2:331/308) per
  140.  l'aiuto fornito nella chiusura del pacchetto e per la spietata revisione
  141.  critica della documentazione.
  142.  Inoltre, gli autori desiderano anche ringraziare Edina Patetta per la
  143.  pazienza dimostrata e per il supporto morale.
  144.  
  145.  
  146.  1 INTRODUZIONE
  147.  
  148.  Questo capitolo vuole essere un'introduzione ragionata al mondo di LAAMEB,
  149.  che e' il mondo della minimizzazione di espressioni booleane, con un occhio
  150.  di riguardo agli algoritmi impiegati per risolvere questa classe di
  151.  problemi. Il paragrafo 1.0 contiene un breve cappello sull'algebra e
  152.  l'aritmetica di Boole e puo' quindi essere saltato da chi e' in possesso di
  153.  queste conoscenze.
  154.  
  155.  1.0 L'ARITMETICA BOOLEANA
  156.  
  157.  Dato che LAAMEB si occupa di funzioni booleane e' necessario fornire un
  158.  minimo di background riguardo a questo argomento.
  159.  Una funzione o espressione booleana puo' essere caratterizzata in molti
  160.  modi. Uno dei piu' classici e' l'uso di una tabella di verita' del tipo
  161.  
  162.                               a  b  |  a or b
  163.                              -------+--------
  164.                               0  0  |    0
  165.                               0  1  |    1
  166.                               1  0  |    1
  167.                               1  1  |    1
  168.  
  169.  Il linguaggio delle espressioni booleane e' quello dell'algebra di Boole,
  170.  che si basa su un dominio caratterizzato da due diversi valori, 0 o falso e
  171.  1 o vero, composti opportunamente mediante le funzioni AND, OR, NOT con le
  172.  seguenti tabelle di verita' (quella dell'OR e' stata data precedentemente):
  173.  
  174.              a  b  |  a and b                     a  |  not a
  175.             -------+---------                    ----+-------
  176.              0  0  |     0                        0  |   1
  177.              0  1  |     0                        1  |   0
  178.              1  0  |     0
  179.              1  1  |     1
  180.  
  181.  Queste sole semplici operazioni vengono usate per costruire funzioni anche
  182.  molto complesse. A seconda del contesto si possono interpretare le funzioni
  183.  and, or e not come moltiplicazione, addizione e opposto dell'aritmetica
  184.  booleana piuttosto che come intersezione, unione e complementare
  185.  insiemistico. Ricordiamo inoltre che, per quanto concerne le priorita', il
  186.  not e' l'operazione a priorita' piu' elevata, seguito da and e or
  187.  nell'ordine.
  188.  Se intese nel senso dell'aritmetica booleana le operazioni suddette godono
  189.  delle normali proprieta' dell'aritmetica dei numeri, come la commutativita',
  190.  l'associativita', ecc.
  191.  A noi interessa piu' da vicino il discorso dell'aritmetica booleana e quindi
  192.  fissiamo, da un punto di vista notazionale, le seguenti convenzioni:
  193.     - A meno che non vi sia una necessita' specifica esprimeremo and, or e
  194.       not in termini di aritmetica booleana e quindi
  195.                                 a and b --> a * b
  196.  LAAMEB 1.01                                                        pag.  5
  197.  
  198.                                 a or b  --> a + b
  199.                                 not a   --> A
  200.     - In merito proprio all'uso del not e' da intendersi che useremo le
  201.       lettere minuscole per le variabili semplici e quelle maiuscole per
  202.       quelle negate.
  203.     - A meno che non vi sia una necessita' specifica ometteremo l'uso di *
  204.       per indicare l'and e concateneremo semplicemente le variabili coinvolte
  205.       nell'espressione. Cosi' facendo otterremo cose come
  206.                                 a * b * c --> abc
  207.     - In virtu' di quest'ultima convenzione useremo solo ed esclusivamente
  208.       variabili il cui nome sia identificato da un'unica lettera.
  209.  
  210.  Esempio: seguendo questa serie di convenzioni il normale or esclusivo
  211.           (funzione che vale 1 quando i suoi argomenti sono diversi) potrebbe
  212.           essere espresso come
  213.                          XOR(a, b) = Ab + aB
  214.  
  215.  Quando una funzione booleana e' espressa in questa forma si dice che e' in
  216.  forma SP, ovvero somma di prodotti, in quanto e' caratterizzata da una somma
  217.  di una serie di termini, espressi come prodotti di variabili semplici o
  218.  negate. Un termine e' definito proprio come uno qualsiasi di questi
  219.  prodotti. Da quanto detto e' evidente che si potrebbero immaginare funzioni
  220.  in molte variabili e a valori in domini di cardinalita' n-esima, con n
  221.  generico. Nel nostro caso pero' ci occuperemo solo di funzioni che hanno un
  222.  unico valore, e che possono quindi essere espresse completamente mediante
  223.  un'unica tabella di verita'.
  224.  Noi utilizzeremo due diverse forme per specificare la funzione da
  225.  minimizzare e quella minimizzata. Nel primo caso identificheremo la funzione
  226.  in ingresso in modo univoco mediante l'elenco dei mintermini che la
  227.  compongono e del numero di variabili che ne fanno parte, mentre nel secondo
  228.  useremo la forma SP.
  229.  Un mintermine e' un 1 della funzione, ovvero una configurazione binaria
  230.  delle variabili in ingresso per cui la funzione vale 1. Questa
  231.  configurazione viene interpretata come numero in base 2 e il mintermine
  232.  viene solitamente espresso nel suo corrispettivo in base 10.
  233.  
  234.  Esempio: vediamo come si esprime in mintermini la seguente funzione
  235.           f(a, b, c, d) a 4 variabili, identificata da questa tabella di
  236.           verita'
  237.  
  238.                  a  b  c  d  |  f
  239.                 -------------+----
  240.                  0  0  0  0  |  1    --> mintermine 0
  241.                  0  0  0  1  |  1    -->      "     1
  242.                  0  0  1  0  |  1    -->      "     2
  243.                  0  0  1  1  |  0
  244.                  0  1  0  0  |  0
  245.                  0  1  0  1  |  0
  246.                  0  1  1  0  |  1    -->      "     6
  247.                  0  1  1  1  |  1    -->      "     7
  248.                  1  0  0  0  |  1    -->      "     8
  249.                  1  0  0  1  |  0
  250.                  1  0  1  0  |  1    -->      "     10
  251.                  1  0  1  1  |  0
  252.                  1  1  0  0  |  1    -->      "     12
  253.                  1  1  0  1  |  0
  254.                  1  1  1  0  |  1    -->      "     14
  255.                  1  1  1  1  |  1    -->      "     15
  256.  
  257.           La funzione f puo' quindi essere espressa come
  258.  
  259.                            Σ4(0,1,2,6,7,8,10,12,14,15)
  260.  
  261.  LAAMEB 1.01                                                        pag.  6
  262.  
  263.           dove 4 e' il numero delle variabili che la compongono (in genere si
  264.           parte da a in ordine alfabetico e quindi a, b, c, d), Σ esprime la
  265.           forma SP e i numeri 0, 1, 2, 6, 7, 8, 10, 12, 14, 15 fra parentesi
  266.           esprimono l'elenco dei mintermini che la costituiscono.
  267.  
  268.  Questo tipo di notazione deriva direttamente dalle mappe di Karnaugh, forma
  269.  tabellare di rappresentazione delle funzioni booleane utilizzate proprio per
  270.  la minimizzazione manuale di semplici funzioni (fino a 5 variabili).
  271.  
  272.  Gli ultimi concetti che devono essere appresi per poter parlare di
  273.  minimizzazione sono quelli legati agli implicanti di una funzione, gli
  274.  implicanti primi, le tabelle cicliche e le forme irriducibili, da cui
  275.  discendono le forme minime, obiettivo dell'elaborazione di LAAMEB, ma
  276.  saranno trattati tutti in modo esauriente piu' avanti.
  277.  
  278.  1.1 CHE COS'E' LAAMEB?
  279.  
  280.  LAAMEB, acronimo che sta per Laboratorio di Analisi Algoritmi di
  281.  Minimizzazione di Espressioni Booleane, e' un programma per la valutazione
  282.  di algoritmi, tempi di esecuzione e bonta' delle soluzioni, nell'ambito
  283.  della minimizzazione di espressioni booleane. L'algoritmo base implementato
  284.  ed analizzato è quello di Quine-McCluskey, descritto nel Luccio, la cui
  285.  esecuzione si divide in 2 fasi, A e B, descritte ed analizzate più
  286.  dettagliatamente nel prosieguo. LAAMEB puo' essere pensato quindi come un
  287.  sistema tramite il quale e' possibile inserire delle funzioni booleane,
  288.  minimizzarle e valutare la validita' della minimizzazione mediante la
  289.  redirezione di statistiche opportune.
  290.  
  291.  1.2 L'ALGORITMO DI MINIMIZZAZIONE DI QUINE-MCCLUSKEY
  292.  
  293.  Come gia' accennato LAAMEB si basa su di un particolare algoritmo di
  294.  minimizzazione, quello detto di Quine-McCluskey. Questo algoritmo deriva
  295.  dall'applicazione del ben noto teorema dell'algebra di Boole detto di De
  296.  Morgan e corrisponde all'utilizzo delle mappe di Karnaugh nella
  297.  minimizzazione manuale.
  298.  L'algoritmo e' diviso in due fasi, dette banalmente fase A e fase B. Nella
  299.  prima fase, partendo dall'elenco dei mintermini forniti, viene generato,
  300.  attraverso iterazioni successive, l'elenco degli implicanti primi. Un
  301.  implicante e' una configurazione particolare di variabili all'ingresso il
  302.  cui valore di verita' (1), implica la verita' anche della funzione intera.
  303.  Ad esempio nel caso della funzione data prima, il mintermine 6, identificato
  304.  anche da AbcD, e' un implicante della funzione. Infatti, quando AbcD = 1 si
  305.  verifica necessariamente che anche f = 1, in quanto affinche' AbcD sia 1
  306.  deve essere per forza a = 0, b = 1, c = 1 e d = 0 e percio' f(a, b, c, d) =
  307.  1. I mintermini sono gli implicanti base, quelli di partenza. Applicando
  308.  successivamente un certo tipo di calcolo si vengono a fondere certi
  309.  implicanti l'uno con l'altro, con l'obiettivo di arrivare all'insieme di
  310.  implicanti primi della funzione. Questi implicanti vengono detti primi, in
  311.  quanto caratterizzati dal fatto che non sono implicati da nessun altro
  312.  implicante. Nell'esempio di prima il mintermine AbcD non puo' essere un
  313.  implicante primo, perche' e' implicato dall'implicante Abc, che a sua volta
  314.  non e' primo in quanto implicato dall'implicante bc, che invece e' primo. E'
  315.  abbastanza facile verificare la veridicita' di queste affermazioni. Questo
  316.  e' comunque cio' che avviene durante la fase A, che e' quella meno pesante
  317.  da un punto di vista del calcolo.
  318.  Durante la fase B, invece, vengono costruite delle tabelle dove sulle righe
  319.  si indicizzano gli implicanti primi ottenuti dalla fase A, mentre sulle
  320.  colonne si indicizzano i mintermini. In questa fase si cerca innanzitutto di
  321.  costruire un insieme di implicanti primi che copra tutti i mintermini (non
  322.  bisogna cioe' "dimenticare" nessun 1 della funzione, altrimenti otterremo
  323.  una funzione diversa) e che sia privo di implicanti primi superflui. Un
  324.  insieme siffatto viene detto forma irridondante della funzione e corrisponde
  325.  all'eliminazione dalla scrittura della funzione di tutti gli implicanti
  326.  LAAMEB 1.01                                                        pag.  7
  327.  
  328.  primi che non sono necessari in qualche forma SP. Ad esempio nella solita
  329.  funzione di prima l'elenco degli implicanti primi e':
  330.                              ABC, BD, cD, aD, bc
  331.  Questi implicanti non concorrono tutti a formare la soluzione minima. Se si
  332.  pigliassero in toto si avrebbe l'espressione:
  333.                            ABC + BD + cD + aD + bc
  334.  che ha la stessa tabella di verita' di f, ma non e' l'espressione minima.
  335.  Infatti, come si puo' facilmente constatare, l'espressione:
  336.                              ABC + cD + aD + bc
  337.  corrisponde ugualmente alla funzione f, ma e' costituita da un numero minimo
  338.  di implicanti. L'esecuzione dell'algoritmo di Quine-McCluskey garantisce che
  339.  l'insieme trovato al termine dell'esecuzione sia irridondante e minimo. E'
  340.  bene precisare una cosa a questo punto: una forma irridondante non e'
  341.  necessariamente minima, mentre e' vero il contrario. La ricerca della forma
  342.  minima di un'espressione booleana avviene quindi nello spazio delle forme
  343.  irridondanti dell'espressione. In realta' poi, la ricerca si estende anche a
  344.  forme ridondanti: cio' e' dovuto al modo in cui gli algoritmi forzano la
  345.  riduzione di una tabella ciclica (vedi sotto). Si rimanda alla letteratura
  346.  specialistica per un approfondimento riguardo a questo argomento.
  347.  Se l'algoritmo viene interrotto e non puo' terminare l'esecuzione, l'unica
  348.  garanzia data e' la copertura della funzione da parte della soluzione
  349.  parziale.
  350.  Nel corso dell'esecuzione della fase B, come detto, l'elemento sul quale si
  351.  lavora e' una tabella, detta ciclica. Senza entrare nel merito del
  352.  significato della ciclicita' di tali tabelle, va detto che la minimizzazione
  353.  di siffatte tabelle viene effettuata mediante criteri non deterministici
  354.  esaustivi, che vanno cioe' a considerare tutte le possibili ramificazioni
  355.  dovute ad una scelta non deterministica. Dopo aver effettuato una di queste
  356.  scelte e' facile che se ne debbano compiere altre sulla strada che si e'
  357.  presa: questo genera ulteriori ramificazioni, che a loro volta possono
  358.  ramificarsi ancora e cosi' via. Algoritmi di questo tipo, che presentano
  359.  cioe' una fase di "branching", presentano tempi di complessita' di tipo
  360.  esponenziale, e vengono risolti con implementazioni di tipo ricorsivo.
  361.  Nel nostro caso il tempo di esecuzione e' dell'ordine di 2^(2^I) nel caso
  362.  peggiore, dove I e' il numero di mintermini della funzione.
  363.  L'albero delle scelte che viene generato e' un albero binario, che puo'
  364.  facilmente raggiungere una profondita' di 25, 26 livelli anche per funzioni
  365.  a 6 variabili. Negli esempi presenti in questa documentazione viene
  366.  descritta l'esecuzione della minimizzazione di una funzione di 6 variabili,
  367.  che ha richiesto l'analisi e la riduzione di piu' di 3 milioni di tabelle
  368.  cicliche.
  369.  
  370.  1.3 ASPETTI DI IMPLEMENTAZIONE DEL PROGETTO
  371.  
  372.  L'aspetto sicuramente piu' interessante tra quelli analizzati in fase di
  373.  implementazione del progetto, e' stato la creazione di un meccanismo
  374.  di attraversamento dell'albero delle scelte semplice ed efficiente, che
  375.  permettesse in modo agevole l'interruzione e la ripresa dell'esecuzione. Si
  376.  doveva cioe' implementare un algoritmo di attraversamento di tipo preorder
  377.  molto duttile e maneggevole. Ci si e' orientati allora verso un algoritmo
  378.  iterativo che assolvesse tutte le funzionalita' di tipo ricorsivo della
  379.  natura del problema, seguendo la stessa tecnica che utilizzano certi
  380.  compilatori per sciogliere una ricorsione: l'"end-recursion removal",
  381.  descritta dal Sedgewick nel V capitolo. Questa tecnica fruisce di uno stack,
  382.  nel quale memorizza i nodi che devono ancora essere attraversati. La
  383.  dimensione di questo stack, ovvero il numero di nodi in esso contenuti, da'
  384.  un'idea, a run-time, della profondita' dell'albero delle tabelle cicliche
  385.  per la funzione in minimizzazione. Se si trattasse di un albero completo
  386.  bisognerebbe tenere presente che, se N fosse la sua profondita', 2^N sarebbe
  387.  il numero di nodi di cui esso e' composto, da cui la complessita'
  388.  astronomica di funzioni a prima vista innocue, fenomeno denominato
  389.  esplosione combinatoria.
  390.  Questo algoritmo di attraversamento e' stato implementato in 3 versioni
  391.  LAAMEB 1.01                                                        pag.  8
  392.  
  393.  differenti, denominate Quine I, Quine II, e Fast Quine (per capire quanto
  394.  segue e' necessario aver bene presente come viene simboleggiato un albero
  395.  binario e che tipo di operazioni si fanno su di esso; si consiglia di
  396.  consultare i primi capitoli del Sedgewick per avere informazioni piu'
  397.  approfondite).
  398.  
  399.     - QUINE I: e' l'algoritmo di Quine-McCluskey, come descritto nel Luccio.
  400.                Vengono esaminate tutte le scelte possibili e non viene
  401.                effettuato nessun taglio "intelligente" su queste.
  402.  
  403.     - QUINE II: e' la versione modificata dell'algoritmo di Quine-McCluskey,
  404.                 nella quale un nodo viene esaminato o inserito nello stack
  405.                 solo se questa scelta puo' essere conveniente, ovvero se
  406.                 il numero di implicanti primi che compongono la forma
  407.                 irridondante del nodo e' minore del numero di implicanti
  408.                 primi della soluzione corrente. Infatti, durante le riduzioni
  409.                 successive gli implicanti primi che compongono la forma
  410.                 irridondante possono solo aumentare; va da se' quindi che non
  411.                 si ha nessuna convenienza a prendere in esame nodi
  412.                 svantaggiosi ancora prima della riduzione.
  413.  
  414.     - FAST QUINE: a differenza delle prime 2 versioni questa non assicura
  415.                   il raggiungimento della forma minima, in quanto non esamina
  416.                   tutto l'albero, bensì solo proseguendo lungo direzioni
  417.                   precise.
  418.  
  419.  Ogni algoritmo, e non solo l'ultimo, presenta due diverse direzioni di
  420.  attraversamento, destra o sinistra. Ognuna delle due direzioni corrisponde
  421.  ad un tipo preciso di scelta non deterministica. In pratica si utilizza
  422.  sempre la regola di dominanza verso destra e di essenzialita' verso
  423.  sinistra. Per chi fosse interessato ai concetti di dominanza ed
  424.  essenzialita' si rimanda alla letteratura specializzata (Luccio).
  425.  In generale per quanto riguarda i primi due algoritmi andare a destra
  426.  significa solo che dal padre si andra' a visitare prima il nodo di destra, e
  427.  poi quello di sinistra, compiendo un attraversamento in preordine "inverso",
  428.  del tipo visita-vai_a_destra-vai_a_sinistra; andare a sinistra significa
  429.  invece andare prima a sinistra e poi a destra dopo aver visitato il nodo,
  430.  compiendo  cosi' un classico preorder. Discorso a parte merita l'ultimo
  431.  algoritmo, FAST QUINE, che non vede un albero ma a partire da un certo nodo,
  432.  guardando sempre e solo nella direzione specificata, si comporta come se
  433.  stesse scorrendo una lista, i cui nodi sono contenuti nello stack. In questo
  434.  modo FAST QUINE esamina solo la dorsale di sinistra o quella di destra
  435.  dell'albero (applicando solo l'essenzialita' o solo la dominanza), e porta
  436.  nel primo caso alla foglia all'estremità sinistra e nel secondo alla foglia
  437.  all'estremità destra.
  438.  
  439.  Entrando piu' nei particolari, l'elemento fondamentale della fase B,
  440.  qualunque sia l'algoritmo utilizzato, e' il ciclo di estrazione, riduzione e
  441.  immissione dei nodi nello stack. Le procedure che svolgono questo compito
  442.  sono state scritte nel modo piu' semplice ed efficace possibile, con
  443.  particolare riguardo a quelle di analisi e aggiornamento di una tabella, in
  444.  quanto compongono cio' che viene definito "the inner loop", il ciclo piu'
  445.  interno della fase B. Con questa espressione si intende quel nucleo di
  446.  istruzioni che si trova al livello piu' interno di nidificazione dei cicli,
  447.  e che quindi viene eseguito più frequentemente. E' stato adottato un
  448.  meccanismo particolare di implementazione delle tabelle, viste come dei
  449.  vettori sui quali le celle sono indirizzate con un criterio di spiazzamento.
  450.  Questo permette innanzitutto una gestione rapida e semplice, ed
  451.  un'allocazione dinamica che permette di mantenere diverse funzioni in
  452.  memoria contemporaneamente.
  453.  
  454.  LAAMEB 1.01                                                        pag.  9
  455.  
  456.  2 COME USARE LAAMEB
  457.  
  458.  In questo capitolo viene descritto dettagliatamente il programma nelle sue
  459.  funzionalita', e costituisce quindi, a tutti gli effetti, un manuale d'uso.
  460.  
  461.  2.0 LE VARIE FUNZIONALITA' DEL PROGRAMMA
  462.  
  463.  Il programma presenta un unico parametro sulla linea di comando:
  464.                               LAAMEB [PR_CYCLE]
  465.  Per PR_CYCLE si intende il numero di forme che devono essere paragonate
  466.  affinche' venga effettuato il refresh dei dati a video nel corso della fase
  467.  B. Nel caso di funzioni molto complesse, e' meglio dimensionare questo
  468.  parametro in misura molto elevata, nell'ordine delle migliaia di tabelle,
  469.  per evitare che la maggior parte del tempo di cpu sia speso per fare stampe
  470.  a video della situazione attuale. Ad ogni modo e' sempre possibile
  471.  interrompere l'esecuzione in un momento qualsiasi della fase B, andando a
  472.  visualizzare le statistiche dettagliate, per poi riprendere da dove si era
  473.  interrotto. Il parametro PR_CYCLE deve essere specificato e puo' avere
  474.  valore compreso tra 0 e 65535; il valore 0 indica che non deve essere
  475.  effettuato alcun refresh sino a quando il calcolo di minimizzazione non e'
  476.  terminato.
  477.  Al di la' di questo parametro iniziale il programma presenta un ambiente
  478.  composto da un'ampia area di informazione e menu' a tendina per
  479.  l'interazione con l'utente. La prima schermata, in particolare, da'
  480.  informazioni sull'avvenuta registrazione del programma e sugli autori.
  481.  Passata questa schermata l'utente puo' fondamentalmente compiere 3 diversi
  482.  tipi di azione, ognuna legata ad un menu' (che e' a sua volta descritto in
  483.  un paragrafo particolare e relativi sottoparagrafi):
  484.     - File: si intendono operazioni di caricamento e/o salvataggio di file di
  485.             funzioni, nonche' l'uscita dal programma;
  486.     - Funzione: si intende l'immissione, o il calcolo o la visualizzazione di
  487.                 una funzione, nonche' alcune altre operazioni ad essa
  488.                 collegate;
  489.     - Algoritmo: mediante questo menu' si effettua la scelta dell'algoritmo
  490.                 di minimizzazione.
  491.  Le varie voci dei menu' sono richiamabili spostandosi con i tasti cursore ed
  492.  utilizzando il tasto INVIO (o RETURN) per l'attivazione, una volta raggiunta
  493.  la posizione desiderata.
  494.  Escludendo le fasi di calcolo e redazione delle statistiche, nella meta'
  495.  inferiore dello schermo e' sempre presente una descrizione sommaria delle
  496.  10 funzioni caricate, in forma:
  497.                            Σv(n1,n2,n3,n4,n5,n6,n7,...)
  498.  dove v e' il numero di variabili della funzione, ni e' l'i-esimo mintermine,
  499.  e gli eventuali puntini di interpunzione segnalano la mancanza di spazio per
  500.  la visualizzazione dell'intero elenco di mintermini. Ogni funzione viene
  501.  identificata con il numero assegnatole in questa parte dello schermo,
  502.  dall'immissione fino alla rimozione per salvataggio binario o cancellazione.
  503.  
  504.  2.1 IL MENU' FILE
  505.  
  506.  Permette di eseguire tutte le operazioni di amministrazione dei file,
  507.  nonche' l'uscita dal programma. Le opzioni possibili sono 3:
  508.     - caricamento di un file contenente una o piu' funzioni precedentemente
  509.       salvate in formato binario;
  510.     - salvataggio di una o piu' funzioni in formato binario o di una sola in
  511.       formato testo;
  512.     - uscita dal programma.
  513.  
  514.         2.1.0 Il comando Carica
  515.  Carica da file binario funzioni precedentemente salvate.
  516.  I dati da fornire nella maschera di input sono:
  517.     - nome del file, path compreso (max 99 caratteri).
  518.  Viene quindi richiesta conferma se i dati inseriti sono corretti. Il
  519.  LAAMEB 1.01                                                        pag. 10
  520.  
  521.  programma tenta di caricare tutte le funzioni contenute nel file
  522.  specificato, funzioni che devono essere state salvate precedentemente in
  523.  formato binario, e segnala all'utente eventuali problemi di memoria o di
  524.  spazio per le funzioni (se ne possono avere al massimo 10 contemporaneamente
  525.  in memoria).
  526.  Questa funzione non e' disponibile nella versione SHAREWARE.
  527.  
  528.         2.1.1 Il comando Salva
  529.  Salva funzioni su file.
  530.  Scegliendo tale opzione viene poi richiesto il tipo di file su cui si
  531.  intende salvare la funzione:
  532.     - file di tipo testo: la consultazione del file puo' avvenire solo fuori
  533.       dall'esecuzione del progetto LAAMEB utilizzando un editor qualsiasi. Il
  534.       formato del file testo è il seguente:
  535.                         RISULTATI GENERALI
  536.                         *       Elenco mintermini
  537.                         *       Numero di variabili
  538.                         *       Stato elaborazione
  539.                         *       Generazione input
  540.                         *       Tempo totale di elaborazione
  541.                         RISULTATI FASE A
  542.                         *       Tempo elaborazione
  543.                         *       Numero implicanti primi
  544.                         *       Elenco implicanti primi
  545.                         RISULTATI FASE B
  546.                         *       Tempo elaborazione
  547.                         *       Numero forme prime paragonate
  548.                         *       Numero tabelle cicliche esaminate
  549.                         *       Numero tabelle presenti nello stack
  550.                         *       Numero implicanti soluzione
  551.                         *       Soluzione
  552.            Quest'ultimo campo cambia in base al tipo di soluzione pervenuta,
  553.            che dipende direttamente dal tipo di elaborazione. Le scritte
  554.            possibili sono:
  555.                         SOLUZIONE (forma minima)
  556.                         SOLUZIONE migliore determinata tra le forme esaminate
  557.                         SOLUZIONE migliore corrente
  558.                         (relativo al caso in cui lo stato e' sospeso)
  559.            Nel caso in cui la soluzione risulti 1 costante l'unico implicante
  560.            primo ottenuto e' della forma "- - - - -", cioe' tanti trattini
  561.            quante sono le variabili; tale formato viene visualizzato
  562.            nell'elenco degli implicanti primi in Fase A e viene scritta la
  563.            definizione "1 COSTANTE" nel campo Soluzione della Fase B.
  564.       Tra questi dati non compare l'algoritmo utilizzato nel corso della
  565.       minimizzazione. Questa scelta non deve stupire, in quanto l'utente,
  566.       interrompendo l'esecuzione del calcolo, puo' anche scegliere di
  567.       cambiare l'algoritmo utilizzato. In questo modo non avrebbe molto senso
  568.       anche solo riportare l'ultimo adottato.
  569.  
  570.     - file di tipo binario: tutte le informazioni riguardante una o piu'
  571.       funzioni vengono salvate in un formato opportuno non editabile, per
  572.       poter consentire agevolmente la ripresa in un secondo tempo. In questo
  573.       caso poi le funzioni vengono cancellate dalla memoria.
  574.  
  575.  In entrambi i casi i dati da fornire sono:
  576.     - le funzioni, mediante riferimento numerico
  577.     - nome del file, path compreso  (max 99 caratteri)
  578.  Viene quindi richiesta conferma se i dati inseriti sono corretti.
  579.  Questa funzione non e' disponibile nella versione SHAREWARE.
  580.  
  581.         2.1.2 Esci
  582.  Esce dal programma, chiedendo conferma dell'uscita.
  583.  Inoltre per ogni funzione presente in memoria chiede all'utente se desidera
  584.  LAAMEB 1.01                                                        pag. 11
  585.  
  586.  che queste vengano salvate, con un progressivo automatico del tipo "f#.laa",
  587.  dove con # si intende il riferimento numerico alla funzione.
  588.  
  589.  2.2 IL MENU' FUNZIONE
  590.  
  591.  Permette di eseguire tutte le operazioni inerenti ad una funzione.
  592.  Le opzioni possibili sono 5:
  593.     - immissione di una funzione in uno dei tre modi ammessi, mediante
  594.       elencazione dei mintermini, generazione casuale dei mintermini o
  595.       elencazione delle configurazioni;
  596.     - calcolo della minimizzazione di una funzione attraverso l'algoritmo e
  597.       la direzione specificati;
  598.     - verifica della copertura di una funzione da parte della soluzione
  599.       attualmente disponibile;
  600.     - generazione delle statistiche di elaborazione di una funzione,
  601.       aggiornate allo stato attuale del calcolo;
  602.     - cancellazione di una funzione attualmente in memoria.
  603.  
  604.         2.2.0 Il comando Immetti
  605.  Immette una funzione attraverso uno dei tre modi possibili.
  606.  Una volta scelto il comando di immissione vi sono tre modi ammessi per
  607.  specificare il tipo di immissione, ad ognuno dei quali corrisponde un
  608.  sottocomando. In ognuno dei tre casi e' necessario specificare, come prima
  609.  cosa, il numero delle variabili della nuova funzione, in numero compreso tra
  610.  1 e 26.
  611.     - Elenco: la forma piu' naturale per immettere una funzione e'
  612.       l'elencazione dei suoi mintermini. Questi vengono inseriti nell'ordine
  613.       desiderato in una stringa lunga al massimo 99 caratteri della forma
  614.                          n1, n2, n3-n4, n5, n6-n7, ...
  615.       dove gruppi di mintermini vengono separati dalla virgola, ed ogni
  616.       gruppo puo' essere un mintermine semplice (ad es. 13), oppure un range
  617.       di mintermini (ad es. 23-78, cui corrispondono tutti i mintermini da 23
  618.       a 78 estremi compresi). In questo modo, la funzione precedentemente
  619.       discussa puo' essere immessa come
  620.                          0-2, 6-8, 10, 12, 14, 15
  621.  
  622.     - Casuale: in questo caso si richiede al programma di generare in modo
  623.       pseudo-casuale l'elenco dei mintermini. Questi vengono generati a
  624.       partire da un seme specificato dall'utente, che permettera' quindi in
  625.       seguito la stessa rigenerazione a partire dallo stesso seme. Viene
  626.       richiesto quindi all'utente il numero di mintermini che si desiderano,
  627.       e il seme, che deve essere un numero compreso tra 0 e 65535. Lavorando
  628.       con 4 variabili, richiedere 10 mintermini generati a partire dal seme
  629.       37 vuol dire richiedere i mintermini
  630.                        13, 14, 1, 11, 9, 15, 6, 7, 0, 8
  631.  
  632.     - Configurazioni: ad ogni mintermine, in quanto configurazione di bit 1 o
  633.       0, puo' essere associato il numero di 1 di cui e' composto. Il
  634.       mintermine 13, per esempio, corrisponde a 1101, ed e' quindi composto
  635.       da 3 bit dal valore 1. Lavorando con 4 variabili, richiedere tutte le
  636.       configurazioni di mintermini composte da 1 a 3 bit di valore 1
  637.       significa richiedere tutti i mintermini
  638.                    8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7
  639.  
  640.         2.2.1 Il comando Calcola
  641.  Calcola una funzione.
  642.  Tramite questo comando viene avviato il calcolo della minimizzazione della
  643.  funzione specificata, individuata mediante riferimento numerico. Il calcolo,
  644.  come gia' detto, viene diviso in due fasi: fase A, di calcolo degli
  645.  implicanti primi, e fase B, di calcolo della forma minima fra quelle
  646.  irridondanti. La prima schermata visualizzata e' quella corrispondente alla
  647.  fase A, e non e' interrompibile. Terminata questa fase si puo' abbandonare
  648.  l'elaborazione o iniziare la fase B, notoriamente piu' lunga per le funzioni
  649.  LAAMEB 1.01                                                        pag. 12
  650.  
  651.  computazionalmente piu' pesanti. Per questo motivo la fase B puo' essere
  652.  interrotta in un punto qualsiasi, per poi essere ripresa nel momento
  653.  desiderato. Nel corso di entrambe le fasi vengono visualizzate delle
  654.  informazioni, che fotografano lo stato attuale della minimizzazione, come il
  655.  numero di implicanti primi, la soluzione parziale, il numero di tabelle
  656.  ridotte, ecc. Nel corso della fase A, composta al massimo da 2^V iterazioni
  657.  (dove V e' il numero delle variabili della funzione), queste informazioni
  658.  vengono visualizzate ad ogni iterazione. Durante la fase B, invece, la
  659.  frequenza di aggiornamento delle informazioni a schermo e' regolata, come
  660.  detto, dal parametro PR_CYCLE della linea di comando di LAAMEB. La frequenza
  661.  massima che si puo' avere coincide con il valore 1 di PR_CYCLE: in questo
  662.  caso ogni volta che viene ridotta una tabella ciclica si aggiornano le
  663.  informazioni a schermo. Si consiglia di mantenere elevato questo parametro
  664.  per le funzioni piu' complesse, nell'ordine delle migliaia o decine di
  665.  migliaia di tabelle cicliche.
  666.  
  667.         2.2.2 Il comando Copertura
  668.  Verifica la copertura di una funzione.
  669.  Una funzione in forma SP si puo' dire coperta nel momento in cui i prodotti
  670.  di cui la somma e' composta implicano tutti e soli i mintermini della
  671.  funzione. In pratica, in questo modo si verifica se la forma SP, che
  672.  rappresenta la soluzione corrente, e' veramente equivalente alla funzione
  673.  nella forma iniziale, cioe' espressa mediante i suoi mintermini. Questo
  674.  comando ha una funzione di controllo sull'esattezza del risultato, ed e'
  675.  stato inserito in origine piu' per effettuare comodamente il debugging che
  676.  altro, visto che l'algoritmo di Quine-McCluskey, una volta implementato
  677.  correttamente, garantisce di per se' l'equivalenza delle due forme della
  678.  funzione. Oggi la sua presenza ha solo un valore di controllo formale e per
  679.  questo motivo gli autori hanno preferito lasciarlo.
  680.  Cosi' come per il comando precedente, la funzione che si vuole verificare
  681.  deve essere specificata tramite riferimento numerico.
  682.  
  683.         2.2.3 Il comando Statistica
  684.  Visualizza le statistiche del calcolo di una funzione.
  685.  Mediante questo comando vengono visualizzate a schermo le informazioni
  686.  inerenti alla minimizzazione di una funzione. Queste informazioni sono le
  687.  stesse che vengono stampate su file di testo mediante il comando Salva,
  688.  anche se sono visualizzate con un layout un poco diverso.
  689.  La funzione, di cui si desiderano le statistiche, deve essere naturalmente
  690.  individuata mediante riferimento numerico.
  691.  
  692.         2.2.4 Il comando Cancella
  693.  Cancella una funzione.
  694.  All'interno di LAAMEB possono essere presenti contemporaneamente al massimo
  695.  10 funzioni. Questo numero puo' ulteriormente scendere se si tratta di
  696.  funzioni dall'elaborazione non terminata e composte da grandi tabelle. Per
  697.  far posto a nuove funzioni e' dunque necessario eliminare qualcuna di quelle
  698.  vecchie. Come gia' detto il comando Salva su file binario elimina
  699.  automaticamente dalla memoria la funzione salvata. Se non si vogliono
  700.  salvare le informazioni su file e' possibile semplicemente cancellare una
  701.  funzione dalla memoria tramite il comando Cancella, specificandola
  702.  attraverso il solito riferimento numerico.
  703.  Attenzione: una volta cancellata una funzione e' definitivamente persa, e
  704.  deve essere manualmente reimmessa nel caso in cui si desideri nuovamente la
  705.  soluzione.
  706.  
  707.  2.3 IL MENU' ALGORITMO
  708.  
  709.  Con il menu' algoritmo l'utente puo' scegliere il tipo di algoritmo da
  710.  utilizzare per la prossima elaborazione. Gli algoritmi a disposizione sono,
  711.  come detto, tre: Quine I, Quine II e Fast Quine (per una descrizione
  712.  sommaria degli stessi si rimanda al capitolo 1.3). Di ogni algoritmo si
  713.  hanno a disposizione due diverse direzioni di lavoro, Sinistra e Destra.
  714.  LAAMEB 1.01                                                        pag. 13
  715.  
  716.  E' possibile attivare l'algoritmo voluto spostando la barra evidenziatrice e
  717.  digitando INVIO in corrispondenza della scelta desiderata. In alto a destra,
  718.  sulla barra dei menu', e sempre disponibile una scritta che individua
  719.  l'algoritmo che si sta utilizzando, ad es. Quine II dx.
  720.  
  721.  
  722.  3 LAAMEB AL LAVORO
  723.  
  724.  LAAMEB e' fondamentalmente un programma di calcolo orientato alla
  725.  presentazione e all'analisi delle statistiche del calcolo, percio' il modo
  726.  migliore per presentare LAAMEB e' quello di vederlo sul campo di battaglia.
  727.  Il problema della minimizzazione e' un problema non banale: appartiene alla
  728.  classe dei problemi NP completi, cioe' la cui complessita' di calcolo e' di
  729.  tipo non polinomiale. Come gia' accennato in precedenza, questa complessita'
  730.  e' dovuta alla necessita' di percorrere tutto un albero, che puo'
  731.  raggiungere con notevole facilita' un numero considerevole di livelli. Anche
  732.  se pieni di buchi, si ha tranquillamente a che fare con alberi composti da
  733.  migliaia di nodi, e in certi casi addirittura milioni.
  734.  
  735.  3.0 INTERPRETAZIONE DEI RISULTATI
  736.  
  737.  Utilizzando LAAMEB con funzioni molto diverse tra loro si giunge ad alcuni
  738.  risultati interessanti. Come detto, la fase A e' quella computazionalmente
  739.  meno preoccupante, anche se si tratta dopotutto di un algoritmo di tipo
  740.  esponenziale, con ordine di complessita' di 2^I, I numero dei mintermini
  741.  della funzione. I tempi di fase A piu' lunghi sono quelli relativi a
  742.  funzioni quasi "piene": con questa espressione si intendono funzioni con un
  743.  elevato numero di mintermini, al limite tutti i mintermini possibili, che
  744.  sono 2^V (V numero delle variabili della funzione). La funzione che ha tutti
  745.  i mintermini possibili presenta un tempo di fase A rilevante (dipendente
  746.  comunque anche da V, in quanto il numero di iterazioni della fase A e' al
  747.  massimo proprio V) e un tempo di fase B nullo, perche' al termine della fase
  748.  A si puo' immediatamente constatare che si tratta della funzione 1 costante.
  749.  Nei casi in cui si osservano tempi lunghi di fase A, si hanno solitamente
  750.  soluzioni abbastanza brevi in fase B, il cui ordine di complessita' e'
  751.  comunque esponenziale del precedente, cioe' 2^(2^I). L'elevato tempo di fase
  752.  A corrisponde quasi sempre alla produzione di un numero di implicanti primi
  753.  molto basso, al limite nessuno nel caso di 1 costante. Nel momento in cui vi
  754.  siano pochi implicanti primi e' praticamente impossibile che si creino
  755.  tabelle cicliche, e quindi la fase B termina in un solo passo di riduzione.
  756.  La fase B e' quella che merita maggiore attenzione. Dopo un certo numero di
  757.  prove si e' osservato che il tempo di elaborazione dipende naturalmente dal
  758.  numero di tabelle cicliche ridotte. Questo numero e' direttamente collegato
  759.  al numero e alla forma degli implicanti primi prodotti in fase A, cioe' il
  760.  numero di tabelle cicliche da ridurre aumenta con l'aumentare degli
  761.  implicanti primi e soprattutto aumenta mostruosamente nel momento in cui gli
  762.  implicanti primi hanno una forma molto omogenea tra loro. Un esempio di
  763.  questo fenomeno e' la funzione dell'esempio 1, descritta nel paragrafo
  764.  successivo, che, a fronte di 50 mintermini genera 90 implicanti primi, tutti
  765.  composti da 4 variabili. Proprio questa omogeneita' negli implicanti primi
  766.  genera un numero elevatissimo di tabelle cicliche da ridurre (piu' di 3
  767.  milioni per l'esempio 1). Sarebbe interessante studiare il legame tra forma
  768.  degli implicanti primi e tabelle cicliche, ma questo argomento va al di la'
  769.  dello scopo del nostro lavoro.
  770.  Le funzioni piu' pesanti sono proprio quelle generate come la funzione
  771.  dell'esempio 1, immesse cioe' tramite il meccanismo delle configurazioni di
  772.  bit. Le funzioni migliori si hanno richiedendo range di configurazioni, e
  773.  per l'esattezza i range centrali, come e' il caso dell'esempio 1.
  774.  Utilizzando gli altri due meccanismi di immissione (Elenco o Casuale), le
  775.  funzioni piu' significative vengono create scegliendo un numero non troppo
  776.  elevato di mintermini, ma anche non troppo basso, distribuito uniformemente
  777.  sull'arco delle configurazioni possibili. Sembra quindi che i risultati piu'
  778.  importanti vengano raggiunti stando nel mezzo, adottando una giusta misura e
  779.  LAAMEB 1.01                                                        pag. 14
  780.  
  781.  sensibilita' nella selezione dei mintermini.
  782.  Da un punto di vista dell'algoritmo utilizzato, non si riscontrano
  783.  prestazioni sostanzialmente differenti utilizzando lo stesso algoritmo nelle
  784.  due direzioni ammesse. Cio' che cambia e' tipicamente l'elenco dei
  785.  mintermini che compongono il minimo, e non il numero totale, facendo
  786.  presupporre che in realta' esistano molti minimi diversi della stessa
  787.  funzione.
  788.  Il comportamento dei tre algoritmi e' invece molto diverso da caso a caso.
  789.  Quine I esamina in modo esauriente l'albero delle scelte, ed e' quello fra i
  790.  tre che ha i tempi di esecuzione piu' elevati, nonche' i parametri di
  791.  minimizzazione (forme prime paragonate, tabelle cicliche esaminate)
  792.  numericamente piu' grandi. Quine II presenta degli abbattimenti notevoli
  793.  nelle dimensioni di questi parametri, in special modo nel numero di forme
  794.  prime paragonate, ma non del tempo di elaborazione: questo si riduce di una
  795.  frazione piccolissima, tanto da poter essere osservata solo su funzioni
  796.  pesanti, come quella dell'esempio 1. Cio' e' dovuto principalmente al fatto
  797.  che il tempo di elaborazione non dipende tanto dal numero di forme
  798.  paragonate, quanto dalle tabelle ridotte, numero diminuito in maniera meno
  799.  sensibile. Inoltre le funzioni di riduzione delle tabelle sono molto
  800.  efficienti, e l'introduzione di un calcolo per il taglio di soluzioni
  801.  svantaggiose aggiunge un tempo di elaborazione che e' solo leggermente
  802.  inferiore a quello di riduzione tagliato. Fast Quine, invece, ha un tempo di
  803.  elaborazione lineare, e non piu' esponenziale, in quanto non permette il
  804.  fenomeno dell'esplosione combinatoria, a prezzo della qualita' della
  805.  soluzione. Come si puo' notare nell'esempio 1, pero', a fronte di
  806.  un'esecuzione di 3 secondi (Fast Quine dx), il programma fornisce una
  807.  soluzione contenente 16 implicanti primi, contro i 15 del minimo (ottenuto
  808.  pero' con un'elaborazione di piu' di 10 ore!). Logicamente non si ha nessuna
  809.  garanzia sulla qualita' della soluzione fornita da questo algoritmo, anche
  810.  se in generale si tratta di una buona approssimazione.
  811.  
  812.  3.1 ALCUNI ESEMPI INTERESSANTI
  813.  
  814.  Gli esempi successivi sono stati ottenuti tutti mediante elaborazione con un
  815.  algoritmo unico, cioe' senza interruzione, e con PR_CYCLE pari a 10000. Il
  816.  computer utilizzato e' un PC desktop con microprocessore Intel 80486 DX 33
  817.  MHz, cache di 64 Kb, e RAM di 4 Mb (anche se attualmente vengono utilizzati
  818.  solo i primi 640 Kb di memoria convenzionale). Prestazioni sensibilmente
  819.  migliori potrebbero essere ottenute con un microprocessore Intel 80486 DX2
  820.  66 MHz o equivalenti, e aumentando fino a 256 Kb la cache on-board.
  821.  Ogni esempio e' stato salvato su file mediante la funzione salva-testo. Per
  822.  ogni esempio si hanno 6 file, corrispondenti alle 6 combinazioni di metodi e
  823.  direzioni di minimizzazione. Ad ogni file e' stato poi aggiunto l'algoritmo
  824.  utilizzato in fase B, in modo tale da renderne piu' efficiente la lettura.
  825.  
  826.  Esempio 1: 6 variabili, configurazioni da 2 a 4 uni
  827.   - Quine I dx    (es11.txt): tempo 10:06:31, forme 3449719, tabelle 3449718,
  828.                               15 implicanti primi nella soluzione
  829.   - Quine I sx    (es12.txt): tempo 10:06:31, forme 3449719, tabelle 3449718,
  830.                               15 implicanti primi nella soluzione
  831.   - Quine II dx   (es13.txt): tempo 10:03:19, forme 1418396, tabelle 3371359,
  832.                               15 implicanti primi nella soluzione
  833.   - Quine II sx   (es14.txt): tempo 10:03:57, forme 1500353, tabelle 3376771,
  834.                               15 implicanti primi nella soluzione
  835.   - Fast Quine dx (es15.txt): tempo 00:00:03, forme       1, tabelle      29,
  836.                               16 implicanti primi nella soluzione
  837.   - Fast Quine sx (es16.txt): tempo 00:00:01, forme       1, tabelle      12,
  838.                               18 implicanti primi nella soluzione
  839.  
  840.  Esempio 2: 8 variabili, elenco: 10-20,40-50,70-80,100-110,130-140,170-180,
  841.                                  200-210,230-240
  842.   - Quine I dx    (es21.txt): tempo 00:00:02, forme     162, tabelle     161,
  843.                               24 implicanti primi nella soluzione
  844.  LAAMEB 1.01                                                        pag. 15
  845.  
  846.   - Quine I sx    (es22.txt): tempo 00:00:01, forme     162, tabelle     161,
  847.                               24 implicanti primi nella soluzione
  848.   - Quine II dx   (es23.txt): tempo 00:00:01, forme      75, tabelle     161,
  849.                               24 implicanti primi nella soluzione
  850.   - Quine II sx   (es24.txt): tempo 00:00:01, forme      75, tabelle     161,
  851.                               24 implicanti primi nella soluzione
  852.   - Fast Quine dx (es25.txt): tempo 00:00:00, forme       1, tabelle       8,
  853.                               24 implicanti primi nella soluzione
  854.   - Fast Quine sx (es26.txt): tempo 00:00:00, forme       1, tabelle       4,
  855.                               24 implicanti primi nella soluzione
  856.  
  857.  Esempio 3: 8 variabili, elenco: 10-20,40-50,70-80,100-110,130-140,160-170,
  858.                                  190-200,220-230
  859.   - Quine I dx    (es31.txt): tempo 00:04:09, forme   14496, tabelle   14495,
  860.                               23 implicanti primi nella soluzione
  861.   - Quine I sx    (es32.txt): tempo 00:04:08, forme   14496, tabelle   14495,
  862.                               23 implicanti primi nella soluzione
  863.   - Quine II dx   (es33.txt): tempo 00:04:08, forme   10000, tabelle   14495,
  864.                               23 implicanti primi nella soluzione
  865.   - Quine II sx   (es34.txt): tempo 00:04:08, forme   10012, tabelle   14495,
  866.                               23 implicanti primi nella soluzione
  867.   - Fast Quine dx (es35.txt): tempo 00:00:01, forme       1, tabelle      16,
  868.                               23 implicanti primi nella soluzione
  869.   - Fast Quine sx (es36.txt): tempo 00:00:01, forme       1, tabelle       9,
  870.                               24 implicanti primi nella soluzione
  871.  
  872.  Esempio 4: 8 variabili, generazione casuale di 240 mintermini a partire dal
  873.             seme 23
  874.   - Quine I dx    (es41.txt): tempo 00:08:28, forme   27199, tabelle   27198,
  875.                               21 implicanti primi nella soluzione
  876.   - Quine I sx    (es42.txt): tempo 00:08:28, forme   27199, tabelle   27198,
  877.                               21 implicanti primi nella soluzione
  878.   - Quine II dx   (es43.txt): tempo 00:08:14, forme    1312, tabelle   22497,
  879.                               21 implicanti primi nella soluzione
  880.   - Quine II sx   (es44.txt): tempo 00:08:16, forme    1881, tabelle   22922,
  881.                               21 implicanti primi nella soluzione
  882.   - Fast Quine dx (es45.txt): tempo 00:00:19, forme       1, tabelle      14,
  883.                               23 implicanti primi nella soluzione
  884.   - Fast Quine sx (es46.txt): tempo 00:00:19, forme       1, tabelle      10,
  885.                               25 implicanti primi nella soluzione
  886.  
  887.  Esempio 5: 5 variabili, elenco: 10-30
  888.   - Quine I dx    (es51.txt): tempo 00:00:00, forme       2, tabelle       1,
  889.                               5  implicanti primi nella soluzione
  890.   - Quine I sx    (es52.txt): tempo 00:00:00, forme       2, tabelle       1,
  891.                               5  implicanti primi nella soluzione
  892.   - Quine II dx   (es53.txt): tempo 00:00:00, forme       2, tabelle       1,
  893.                               5  implicanti primi nella soluzione
  894.   - Quine II sx   (es54.txt): tempo 00:00:00, forme       2, tabelle       1,
  895.                               5  implicanti primi nella soluzione
  896.   - Fast Quine dx (es55.txt): tempo 00:00:00, forme       1, tabelle       1,
  897.                               5  implicanti primi nella soluzione
  898.   - Fast Quine sx (es56.txt): tempo 00:00:00, forme       1, tabelle       1,
  899.                               5  implicanti primi nella soluzione
  900.  
  901.  
  902.  4 PROSPETTIVE
  903.  
  904.  LAAMEB non e' un programma chiuso, ma in quanto laboratorio si puo'
  905.  intendere in continua evoluzione. Questo capitolo vuole gettare un veloce
  906.  sguardo verso quello che puo' essere il futuro del prodotto, partendo da
  907.  dove e' nato e valutandone le prospettive.
  908.  
  909.  LAAMEB 1.01                                                        pag. 16
  910.  
  911.  4.0 COME E' NATO LAAMEB
  912.  
  913.  Il programma e' nato come tesina per l'esame di Sistemi di Automazione 1,
  914.  del II anno di corso della facolta' di Scienze dell'Informazione, di cui il
  915.  prof. Torelli e' titolare. Fin dal primo momento, tutte le risorse degli
  916.  autori sono state indirizzate verso l'ottimizzazione degli algoritmi
  917.  implementati, perdendo un po' di vista l'aspetto riguardante l'interfaccia
  918.  utente. Quest'ultima e' stata realizzata utilizzando delle finestre a
  919.  carattere, senza mettere in atto meccanismi particolari di overlap o che
  920.  velocizzassero l'accesso a video, come si puo' notare su macchine
  921.  particolarmente lente. Questa prima release di LAAMEB vuole solo essere solo
  922.  uno strumento valido, efficace e il piu' possibile veloce nel calcolo della
  923.  minimizzazione.
  924.  
  925.  4.1 COME POTRA' EVOLVERSI
  926.  
  927.  L'evoluzione di LAAMEB puo' avvenire su molte linee; cercheremo qui di
  928.  riportare quelle principali individuate dagli autori:
  929.  
  930.   - miglioramento dell'interfaccia utente, con gestione automatica di mouse e
  931.     overlapping windows
  932.   - redirezione su stampante delle statistiche
  933.   - arricchimento delle statistiche di minimizzazione, riportando ad es. la
  934.     lista dei minimi incontrati e la tabella in corrispondenza della quale si
  935.     ha avuto il minimo
  936.   - funzione di salvataggio periodico nelle elaborazioni piu' pesanti
  937.   - inserimento di euristiche nella ricerca del minimo, sia a livello
  938.     dell'ordine di valutazione degli algoritmi esaustivi, sia a livello del
  939.     taglio delle possibili soluzioni per algoritmi che non conducono al
  940.     minimo
  941.   - implementazione di particolari algoritmi per il calcolo degli implicanti
  942.     primi, che permettano un taglio iniziale degli stessi, con conseguente
  943.     abbattimento drastico delle tabelle cicliche da esaminare
  944.   - allargamento delle minimizzazione a funzioni con piu' di 8 variabili
  945.   - implementazione di algoritmi di minimizzazione che rendano minimo il
  946.     numero di porte and, a parita' di porte or
  947.  
  948.  Chiunque fosse interessato a collaborare nella messa a punto di release
  949.  future del pacchetto, o abbia dei quesiti particolari, e' pregato di
  950.  rivolgersi, previa registrazione, a Giuliano Bossi, attraverso una delle
  951.  modalita' riportate all'inizio di questa documentazione.
  952.  
  953.  
  954.  5 BIBLIOGRAFIA
  955.  
  956.  1) LUCCIO F., PAGLI L., "Reti logiche e calcolatore", 1986,
  957.     Bollati Boringhieri
  958.  2) SEDGEWICK R., "Algorithms in C", 1990, Addison-Wesley
  959.